3. Matrice rara

3.1 Conditia de existenta

3.2 Reprezentare prin vectori
3.3 reprezentare prin liste
3.4 Reprezentare prin liste de liste
3.5 Creare
3.6 Opertatii aritmetice

3.7 Normalizarea

3.8 Conversia

3.9 Testarea calitatii procedurilor

3.10 Lungimile zonelor de memorie ocupate de diferite reprezentari pentru matrice rare

back data structures curricula

3.1 Conditia de existenta
O matrice este considerata rara atunci cand folosind o alta modalitate de memorare a elementelor se obtine un grad de utilizare superior memorarii element cu element.
Matricea:
0 0 0 2 9 0 0 0 0 0
1 0 0 3 0 0 0 0 5 0
0 0 0 0 0 0 0 0 0 0
0 8 0 0 0 0 0 0 0 7
2 1 0 0 0 0 4 0 0 3
0 0 0 0 0 0 0 2 0 0
9 0 0 0 0 5 0 0 0 1
0 0 0 0 1 8 0 0 0 0
este o matrice rara pentru ca:
- daca este memorata element cu element, fiecare element ocupand K baiti
- daca are M linii si N coloane
lungimea zonei de memorie LM necesara este
LM=K*M*N baiti.
Pentru cazul dat
K=2
M=8
N=10
LM=2*8*10=160 baiti.
Se observa ca matricea contine multe elemente nule.
Se pune problema memorarii numai elemente nenule.
Se definesc 3 vectori;
lin[] - pentru memorarea pozitiilor liniilor unde se afla elementele nenule
col[] - pentru memorarea pozitiilor coloanelor unde se afla elementele nenule
val[] - pentru memorarea valorilor elementelor nenule.
Pentru matricea data, cei trei vectori au valorile date in tabelul urmator;
Matricea initiala are 8*10 elemente.br> In cei trei vectori se memoreaza informatii despre elementele nenule, in numar de 15.
Daca:
- lungimea unui element al vectorului lin[] este L1 baiti
- lungimea unui element al vectorului col[] esrte L2 baiti
- lungimea unui element din vectorul val[] este L3 baiti
- numarul elementelor nenule este K
- numarul liniilor matricei initiale este M
- numarul coloanelor matricei initiale este N
- lungimea zonei de memorie ocupata de un element din matricea initiala este L3 baiti, atunci calculul lungimii zonei de memorie LG() ocupata este pentru:
- vectorul unde se memoreaza liniile elementelor nenule LG(lin[])=L1*K
- vectorul unde se memoreaza coloanele elementelor nenule LG(col[])=L2*K
- matricea initiala LG(mat_full[][])=M*N*L3
- vectorul elementelor nenule LG(val[])=K*L3.
Se calculeaza gradul de utilizare, GRU, prin relatia:
GRU=(LG(lin[])+LG(col[])+LG(val[]))/LG(mat_full[][])
Pentru exemplu considerat, daca:
- pozitiile liniilor si coloanelor sunt memorate pe int, LG(lin[i])=2
LG(col[i])=2, LG(val[i])=4, k=15, M=8, N-10
atunci
GRU=(15*2+15*2+15*4)/(8*10*4)=120/320=0,37 Inseamna ca matricea data este o matrice rara.
Daca L1=L2=L3
conditia ca matricea sa fie rara este ca NUMARUL ELEMENTELOR NENULE SA REPREZINTE CEL MULT 33% DIN TOTALUL ELEMENTELOR MATRICEI INITIALE.

element
nenul initializare
lin[] initializare
col[] initializare
val[]

0 lin[]=0 col[]=3 val[]=2

1 lin[]=0 col[]=4 val[]=9

2 lin[]=1 col[]=0 val[]=1

3 lin[]=1 col[]=3 val[]=3

4 lin[]=1 col[]=9 val[]=5

5 lin[5]=3 col[5]=1 val[5]=8

6 lin[]=3 col[]=10 val[]=7

7 lin[]=4 col[]=0 val[]=2

8 lin[]=4 col[]=1 val[]=1

9 lin[9]=4 col[9]=6 val[9]=4

10 lin[]=4 col[]=10 val[]=3

11 lin[]=5 col[]=8 val[]=2

12 lin[]=6 col[]=0 val[]=9

13 lin[13]=6 col[13]=5 val[13]=5

14 lin[14]=6 col[14]=10 val[14]=1

....................
....................
....................
....................
....................
....................
....................
....................
revenire

3.2 Reprezentare prin vectori
Se definesc trei vectori:
- un vector care memoreaza liniile pe care se afla elementele nenule
- un vector pe care se memoreaza coloanele pe care se afla elementele nenule
- valoarea elementelor nenule.
Procedura care initializeaza de la tastatura o matrice rara contine:
- secventa de initializare
- secventa de citire a liniei pe care se afla elementul nenul
- secventa de citire a coloanei pe care se afla elementul nenul
- secventa de introducere a elemntului nenul - mecanismul de incheiere a procesului de introducere elemente nenule
- procedura returneaza numarul elementelor nenule din matrice
- se presupune ca dimensiunea matricei este cunoscuta si nu are legatura cu aceasta procedura.
Cei trei vectori au un grad de incarcare dat de faptul ca intre K si numarul maxim de elemente nenule care se memoreaza efectiv exista diferente.
....................
....................
....................
....................
....................
....................
....................
....................
revenire

3.3 Reprezentare prin liste
Fata de reprezentarea prin cei trei vectori, reprezentarea prin liste se caracterizeaza prin:
- strucutrarea informatiei utile in trei campuri ce memoreaza pozitia liniei, pozitia coloanei, valoarea elementului nenul
- se aloca atatea elemente in lista cate elemente nenule sunt in matricea rara.
Reprezentarea prin liste simple asigura o folosire mai buna a spatiului de memorie, desi pointerii ocupa suficient de mult spatiu, ceea ce impune ca numarul de elemente nenule sa fie mult sub 30% din totalul elementelor matricei.

....................
....................
....................
....................
....................
....................
....................
....................
revenire

3.4 Reprezentare prin liste de liste
Memorarea listelor de liste vizeaza faptul ca memorarea elementelor nenule de pe aceeasi linie apartin unei subliste.
Procesul de cautare este mai bun.
Se demonstreaza ca exista situatii in care acest mod de memorare este neperformant.
De exemplu, cand pe o linie se afla un singur element.
Re prezentarea prin liste de liste
implica aparitia unui numar ridicat de pointeri, demonstrandu-se chiar situatiile in care acest mod este cu totul ineficient.
....................
....................
....................
....................
....................
....................
....................
....................
revenire

3.5 Creare
Cei trei vectori se aloca static.
Initializarea se face de la tastatura.
Pentru lista de liste datele se preiau de la tastatura.
Pentru matricea rara creata cu liste datele se iau de la tastatura.
....................
....................
....................
....................
....................
....................
....................
....................
revenire

3.6 Opertatii aritmetice
- adunarea de matrice rare
- scaderea de matrice rare
- transpunerea de matrice rare
void trans_rar(int lin[], int col[], int val[], int K)
{
int i, temp;
for(i=0;i {
temp=lin[i];
lin[i]=col[i];
col[i]=temp;
}
}
- verificarea daca matricea rara este simetrica - inversarea - rezolvarea de sisteme liniare de ecuatii.
Daca se doreste scaderea
a doua matrice rare se obtine rezultatul
tot ca matrice rara. ....................
....................
....................
....................
....................
....................
....................
....................
revenire

3.7 Normalizarea
Este operatia de eliminare din tripletele de vectori lin[], col[] si val[] a elementelor pentru care val[h]=0. Se produce glisare in interiorul vectorului, cu scaderea valorii lui K. int normalizare(int lin[], int col[], int val[], int K)
{
int valnul, i,knull=0; for(i=0;i if(val[i]==0) {
knull++;
glisare(lin[],knull,K);
glisare(col[],knull,K);
glisare(val[],knull,K);
}
return(knull);
}
glisare() este procedura de stergere a unui element de pe pozitie data dintr-un vector.
....................
....................
....................
....................
....................
....................
....................
....................
revenire

3.8 Conversia
Este procedeul prin care se efectueaza:
- trecerea de la matricea rara la matricea cu toate elementele
void rar_to_full(int matfull[][NRCOL],int lin[], int col[], int val[], int nrnenul, int nrlin, int nrcol)
{
int k,i,j;
for(i=0; i for(j=0;j matfull[i][j]=0;
for(k=0;k {
i=lin[k];
j=col[k];
matfull[i][j]=val[k];
}
}
daca se doreste eliminarea parametrilor nrlin si nrcol, se parcurg elementele vectorilor lin[] si col[] si se extrag valorile maxime;
- trecerea din matrtice completa in matrice rara:
int full_to_rar(int matfull[][NRCOL],int lin[], int col[], int val[], int nrlin, int nrcol)
{
int nrnenul,i,j;
nrnenul=0;
for(i=0; i for(j=0;j if(matful[i][j]!=0)
{
col[nrnenul]=j;
lin[nrnenul]=i;
val[nrnenul]=matful[i][j];
nrnenul++;
}
return9nrnenul);
}
....................
....................
....................
....................
....................
....................
....................
....................
revenire

3.9 Testarea calitatii procedurilor
Procedurile de lucru cu matricele rare trebuie testate cat mai complet.
Procedura de adunare doua matrice rare se testeaza cu seturi de date cat mai diferite.
Setul de date 0001
Matricele rare A si B au acelasi numar de elemente nenule, dispuse pe aceleasi linii si coloane.

A_lin[] A_col[] A_val[] B_lin[] B_vol[] B_val[] C_lin[] C_vol[] C_val[]
0 7 23 0 7 20 0 7 43
4 5 81 4 5 -60 4 5 21
4 17 17 4 17 211 4 17 228
10 37 11 10 37 -12 10 37 -1
20 57 3 20 57 20 20 77 33
Setul de date 0002
Matricele au elemente nenule pe aceleasi pozitii dar valorile lor sunt opuse, ceea ce conduce la o matrice cunumar de elemente nenule egal cu ZERO.

A_lin[] A_col[] A_val[] B_lin[] B_vol[] B_val[] C_lin[] C_vol[] C_val[]
0 7 23 0 7 -23 0 7 0
4 5 81 4 5 -81 4 5 0
4 17 17 4 17 -17 4 17 0
10 37 11 10 37 -11 10 37 0
20 57 3 20 57 -3 20 57 0
Setul de date 0003
Matricea A are elemente nenule pe anumite linii si coloane, iar matricea B are elementele nenule pe cu totul alte linii si coloane.

A_lin[] A_col[] A_val[] B_lin[] B_vol[] B_val[] C_lin[] C_vol[] C_val[]
0 7 23 0 7 - 0 7 23
4 5 81 4 5 - 4 5 81
4 17 17 4 17 - 4 17 17
10 37 11 10 37 - 10 37 11
20 57 3 20 57 - 20 57 3
30 7 - 30 7 20 30 7 20
44 55 - 44 55 -60 44 55 -60
54 67 - 54 67 211 54 67 211
57 77 - 57 77 -12 57 77 -12
80 80 - 80 80 20 80 80 20
Setul de date 0004
Elementele nenule din matricea B mai putine la numar decat cele din matricea A au aceleasi pozitii cu elementele matricei A.
Setul de date 0005
Elementele nenule din matricea A mai putine la numar decat cele din matricea B au aceleasi pozitii cu elementele matricei B.
Setul de date 0006
Cele doua matrice au numai o parte din elementele nenule pe pozitii comune pe liniile 20, 22,27.

A_lin[] A_col[] A_val[] B_lin[] B_vol[] B_val[] C_lin[] C_vol[] C_val[]
0 7 23 0 7 - 0 7 23
4 5 81 4 5 - 4 5 81
4 17 17 4 17 - 4 17 17
10 37 11 10 37 - 10 37 11
20 57 3 20 57 - 20 57 3
20 58 3 20 58 2 20 58 5
22 22 33 22 22 3 22 77 6
27 27 13 27 27 14 27 27 27
30 7 - 30 7 20 30 7 20
44 55 - 44 55 -60 44 55 -60
54 67 - 54 67 211 54 67 211
57 77 - 57 77 -12 57 77 -12
80 80 - 80 80 20 80 80 20
Setul de date 0007
Matricea A nu are elemente nenule, iar matricea A are elemente nenule.
Setul de date 0008
Matricele A si B au elemente nenule oarecare din care:
- unele prin insumare dau valoarea zero
- unele prin insumare dau valoare diferita de zero
- unele nu au corespondent nenul in cealalta matrice
- numarul elementelor nenule din cele doua matrice este oarecare.
Setul de date 0009
Matricea A nu are elemente nenule, iar matricea A are elemente nenule.

Cu cat seturile de date de test reusesc sa acopere mai multe cazuri, cu atat testarea evidentiaza situatii in care se vede daca procedura conduce sau nu la rezultate corecte.
Specificatiile de programare trebuie sa indice seturile de date, proprietatile si sa furnizeze exemple concrete de matrice A si B precum si rezultatele C, sub forma celor 3 vectori.
revenire

3.10 Lungimile zonelor de memorie ocupate de diferite reprezentari pentru matrice rare

Performanta lucrului cu matrice rare este data de calculul gradului de umplere
a matricei initiale.
Pentru a fundamenta corect cu ce tip de reprezentare se lucreaza, trebuie calculata lungimea zonei de memorie
CLG(), pe care o ocupa o matrice completa alocata dinamic.
Daca se lucreaza cu o reprezentare folosind trei vectori este necesar sa se calculeze, de ase,esemenea, lungimea VLG()
a zonei de memorie ocupata de reprezentarile celor NN elemente nenule din matricea rara.
Se observa ca pentru a reprezenta matricea rara sub forma unei liste simple, lungimea LSLG()
a zonei de memorie include si variabilele pointer de lungime L_p.
Lungimea LLLG() a zonei de memorie ocupata de elementele necesare realizarii unei reprezentari pentru matricea rara folosind listele de liste, include:
- elementele listei de baza formata din NLN elemente
- elementele listelor derivate, ce corespund elementelor nenule de pe fiecare linie a matricei initiale.
Pentru a vedea care este reprezentarea cea mai potrivita, se iau pe rand si se compara lungimile zonelor de memorie.
Se stabileste conditia ca reprezentarea prin 3 vectori sa fie mai buna decat reprezentarea ca matrice completa alocata dinamic, impunand ca VLG < CLG.
Se stabileste conditia ca reprezentarea prin lista de liste sa fie mai buna decat reprezentarea ca matrice completa alocata dinamic, impunand ca LLLG < CLG.
In acelasi fel se stabilesc si celelalte cerinte de asigurare a situatiilor in care o reprezentare se dovedeste practic sa fie avantajoasa.
revenire

element nenul	initializare lin[]	initializare col[]	initializare val[]
0	lin[]=0	col[]=3	val[]=2
1	lin[]=0	col[]=4	val[]=9
2	lin[]=1	col[]=0	val[]=1
3	lin[]=1	col[]=3	val[]=3
4	lin[]=1	col[]=9	val[]=5
5	lin[5]=3	col[5]=1	val[5]=8
6	lin[]=3	col[]=10	val[]=7
7	lin[]=4	col[]=0	val[]=2
8	lin[]=4	col[]=1	val[]=1
9	lin[9]=4	col[9]=6	val[9]=4
10	lin[]=4	col[]=10	val[]=3
11	lin[]=5	col[]=8	val[]=2
12	lin[]=6	col[]=0	val[]=9
13	lin[13]=6	col[13]=5	val[13]=5
14	lin[14]=6	col[14]=10	val[14]=1

A_lin[]	A_col[]	A_val[]	B_lin[]	B_vol[]	B_val[]	C_lin[]	C_vol[]	C_val[]
0	7	23	0	7	20	0	7	43
4	5	81	4	5	-60	4	5	21
4	17	17	4	17	211	4	17	228
10	37	11	10	37	-12	10	37	-1
20	57	3	20	57	20	20	77	33